Pictures with thousands or millions colors can be represented as true color images, storing the exact color for each pixel in the formats such as BMP (bitmap) and JPEG. In contrast, pictures containing only a few (typically up to 256) colors can be stored more efficiently as colormapped images or palettized images like the well known GIF (Graphics Interchange Format) or PNG (Portable Network Graphics) format. A significant portion of web images are in the format of GIF or PNG.
When browsing palettized images over low-bandwidth communication links, such as wireless links or dial-up links, progressive transmission of these palette images can support fast browsing since it enables the users to view complete versions of these images (but at a low resolution) before all progressively coded image data has been received. However, even though both GIF and PNG support an interlaced format, which refines the resolution of an image progressively by encoding the image in multiple passes and skipping a number of pixels in each pass, interlaced GIF and PNG are not in a progressive format in the strict sense that the color information of each pixel is refined progressively up to lossless recovery.
Rauschenbach investigated the progressive refinement of color information for palette images in his so-called MCQ (Mobile visualization Color Quantized format) method (U. Rauschenbach, “Compression of palettized images with progressive coding of the color information,” in Proc. SPIE Visual Communications and Image Processing (VCIP2000), Perth, Australia, June 2000, hereinafter referred to as [1]). Unlike the interlaced GIF and PNG formats, the refinement of color information in MCQ is done bit-plane by bit-plane, and allows the early recognition of shapes with fine details (e.g. text), normally after decoding a small portion of the compressed bit stream. Although MCQ supports progressive refinement of color information in contrast to resolution refinement, it only achieves a compression ratio comparable to GIF or PNG format. To improve the compression ratio while supporting the progressive transmission of palette images, Chen et al. (X. Chen, S. Kwong, and J. Feng, “A new compression scheme for color-quantized images,” IEEE Transactions on Circuits and System for Video Technology, Vol. 12, No. 10, pp. 904˜908, October 2002, hereinafter referred to as [2]) proposed a new color refinement scheme based on MCQ and the distortion-based hierarchical splitting color quantization algorithm pioneered by Orchard and Bouman (M. Orchard and C. Bouman, “Color quantization of images,” IEEE Transactions on Signal Processing, Vol. 39, No. 12, pp. 2677˜2690, December 1991, hereinafter referred to as [3]). Unlike MCQ where the color information is refined bit-plane by bit-plane with the number of bit-planes equal to the color depth of the palette, Chen's algorithm refines the color information color by color. For lossless compression of palette images, the color splitting algorithm proposed in [2] achieves around 30˜40% size reduction compared to GIF or PNG format in addition to its decent feature of supporting the progressive transmission.